Secret sharing schemes protect the secrecy and integrity of information by distributing the information over n different locations. The information can only be recovered if one has access to a certain minimal number of locations. In particular, in a (k, n)-threshold scheme, k locations together can reconstruct the secret information, where k−1 locations cannot get any information about it.
In H. Krawczyk et al. “Proactive secret sharing or: How to cope with perpetual leakage” In Crypto '95, pages 339-352, Santa Barbara, 1995, a synchronous proactive secret sharing scheme is presented. Therein, the lifetime of the system is divided into short time periods only, such that it is plausible to assume that an adversary cannot break into more than k−1 locations during one time period. Further, the adversary is assumed to be transient, i.e. corrupted servers can be identified and rebooted, such that the adversary looses control over them, but still remembers the last state of the server. At the beginning of each time period, the system is refreshed such that the information, an adversary gathered in a previous period becomes obsolete. Refreshing the system involves the generation of new random shares of the old secret.
An asynchronous verifiable secret sharing system has been proposed by Ran Canetti and Tal Rabin, “Fast asynchronous Byzantine agreement with optimal resilience” in STOC 93, pages 42-51, New York, 1993, basing on ideas from Feldman and Micali, “An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement”, STOC 88, pages 148-161, New York 1988. This scheme does not use public key cryptography, but has a very high message complexity.
It is an object of the present invention to create a verifiable secret sharing scheme for a potentially asynchronous network capable of tolerating a maximum of t faulty devices, processors or parties. Partially asynchronous network in that sense means that the network can work either in synchronous or asynchronous mode, depending on the circumstances and the given assumptions.
It is a further object of this invention to provide a method to be operable among n processors or parties, where at most t<n/3 processors are faulty, and further where the sharing can be achieved in constant time with the number of messages being exchanged in the order of the square of n.
Glossary
The following are informal definitions to aid in the understanding of the description.
In Asynchronous Verifiable Secret Sharing (AVSS), a secret value x is shared by a dealer or distributor among n parties P1, . . . , Pn such that each coalition of k−1 parties can not compromise x, while any coalition of k or more parties can efficiently construct x. This is also called (k, n) sharing, indicating that k out of n parties are required to reconstruct the secret value x.
Group: A group in the cryptographic sense is an algebraic system (G,*) consisting of a set of elements or numbers and a group operation (*) with some specified properties, where (*) is associative, has a neutral element, and where every element in G has an inverse element.
The choice of the symbol (*) is arbitrary. In fact, the operation of most groups is denoted by either + or ·, and such groups are referred to as additive or multiplicative group, respectively.
For example, for any positive integer q, a set Zq consists of the integers 0, . . . , q−1, and it forms a group under the operation of addition modulo q. Moreover, the subset of Zq consisting of those integers relatively prime to a forms a group under multiplication modulo q, and is denoted Zq*. In particular, if p is prime, then Zq* consists of {1, . . . , p−1}, and is a group with p−1 elements.
Hash function: A hash function is a computationally efficient function mapping binary strings of arbitrary length to binary strings of some fixed length.
Hybrid Failures
The method for achieving Byzantine Agreement can distinguish between several different ways in which a network device can fail. This could for example be
Byzantine Failures BF: If a byzantine failure BF occurs, the adversary has taken full control over the corresponding machine. All secrets this machine has are handed over to the adversary, who now controls its entire behavior.
Crash Failures CF: A crash failure CF simply means that the corresponding machine stops working. This could happen anytime, i.e., even in the middle of a broadcast or while sending a message. It is assumed that there is no mechanism other parties can reliably detect such a crash.
Link Failures LF: A link failure LF occurs when not a party, but an interconnecting link becomes faulty. As the link has no access to authentication keys, it is easy to prevent it from modifying or inserting messages. A faulty link could however delete messages, and it might completely disconnect two parties.
Adversary Structure
An adversary structure T is a set of sets (coalitions) of parties whose corruption the system should tolerate. This generalizes a threshold scheme to be more flexible and adapt to environmental structures.